package cn.orange.ch10_dynamicprogramming;

/**
 * LC279.完全平方数
 */
public class LC279 {
    public int numSquares(int n) {
        //dp[i]：和为i的最少完全平方数为dp[i]
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
        }
        for (int i = 1; i <= n / 2 + 1; i++) {
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], 1 + dp[j - i * i]);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        LC279 alg = new LC279();
        System.out.println(alg.numSquares(12));
        System.out.println(alg.numSquares(13));
    }
}
